//
// Created by LiuYou on 2021/11/30.
//

#include <iostream>
#include <vector>


/*
 * 对 getMid2();函数的简化。
 *
 * 使用了位运算, 比 / 2 更快。
 */
static int getMid3(int l, int r) {
    return l + ((r - l) >> 1);
}


/*
 * 也是求数组的中点位置, 但是不用担心溢出。
 *
 * 但是 return l / 2 + r / 2; 是不行的, 这样取出来的中点有误。
 */
static int getMid2(int l, int r) {
    return l + (r - l) / 2;
}


/**
 * @brief 求数组中点的位置。将数组二分。
 * @param l
 * @param r
 * @return 返回数组中点的位置。
 *
 * @details 这样就分成了两个部分, 左侧部分是 l ~ getMid1(); 右侧部分是 getMid1 + 1 ~ r。
 * 即: 左侧部分为 l ~ mid, 右侧部分为 mid + 1 ~ r。
 *
 * @note (l + r) 可能会溢出。
 */
static int getMid1(int l, int r) {
    return (l + r) / 2;
}


/**
 * @brief arr[L...R]范围上求最大值。
 * @param arr 数组
 * @param l 左侧的位置
 * @param r 右侧的位置
 * @return 在数组 L 到 R 的范围上, 返回最大值。
 *
 * @details 使用了递归的思路找出了最大值。
 *
 * <strong>递归思路在于画出递归树！执行的顺序就是树的遍历顺序(二叉树的后续遍历)。</strong>
 */
static int process(std::vector<int>& arr, int l, int r) {
    // arr[L...R]范围上只有一个数, 直接返回, base case(基线情况)。
    // 只有一个数, 那么最大值就是它自己。
    if (l == r) {
        return arr[l];
    }
    // 如果不止一个数, 就求中点的位置。
    // 为什么求中点位置使用下面这种写法? 防止溢出。
    int mid = l + ((r - l) >> 1);
    int leftMax = process( arr, l, mid );
    int rightMax = process( arr, mid + 1, r );
    return std::max( leftMax, rightMax );
}


static int getMax(std::vector<int>& arr) {
    return process( arr, 0, arr.size() - 1 );
}


static int getMax2(std::vector<int>& arr) {
    int maxIndex = 0;
    for (int i = 0; i < arr.size() - 1; ++i) {
        if (arr[i] > arr[maxIndex]) {
            maxIndex = i;
        }
    }
    return arr[maxIndex];
}


int main(int argc, char** argv) {
    {
        std::vector<int> arr{3, 5, 11, 1, 3, 51415, 5651000, 232, 31, 3, 51341};

        std::cout << getMax( arr ) << std::endl;
        std::cout << getMax2( arr ) << std::endl;
    }


    return 0;
}




/*int main(int argc, char** argv) {
    std::cout << getMid1( 0, 5 ) << std::endl;
    std::cout << getMid2( 0, 5 ) << std::endl;
    std::cout << getMid3( 0, 5 ) << std::endl;

    std::cout << getMid1( 2, 5 ) << std::endl;
    std::cout << getMid2( 3, 5 ) << std::endl;
    std::cout << getMid3( 4, 5 ) << std::endl;


    return 0;
}*/

